package com.leetcode.problems;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * @version: 1.0
 * @author: Vpen
 * @date: 2021/12/11 16:51
 * @content: 倒叙打印链表   {1,2,3} -> [3,2,1]
 */
public class Problem1 {
    public static void main(String[] args) {
        ListNode header = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        header.next = node1;
        node1.next = node2;
        node2.next = node3;
        node4.next = null;

        Solution1_1 list = new Solution1_1();
        System.out.println(list.printListFromTailToHead(header));

        Solution1_2 solutionList2 = new Solution1_2();
        System.out.println(solutionList2.printListFromTailToHead(header));


        Solution1_3 solutionList3 = new Solution1_3();
        System.out.println(solutionList3.printListFromTailToHead(header));


        Solution1_4 solutionList4 = new Solution1_4();
        System.out.println(solutionList4.printListFromTailToHead(header));
    }
}


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

/**
 * 使用栈，先进后出
 *
 * @author Vpen
 * @date 2021/12/11 16:54
 **/
class Solution1_1 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();

        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }
}

/**
 * @author:韦鹏
 * @desc: 使用反向遍历, 原地转置 (错误写法，因为未知元素个数)
 */
class Solution1_2 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Integer[] list = new Integer[4];
        int i = 0;
        while (listNode != null) {
            list[i++] = listNode.val;
            listNode = listNode.next;
        }

        int first = 0;
        int last = list.length - 1;
        while (first < last) {
            Integer f = list[first];
            Integer l = list[last];
            list[first] = l;
            list[last] = f;
            first += 1;
            last -= 1;
        }
        return new ArrayList<>(Arrays.asList(list));
    }
}

/**
 * @author:韦鹏
 * @desc: 使用反向遍历, 原地转置
 */
class Solution1_3 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        int first = 0;
        int last = list.size() - 1;
        while (first < last) {
            Integer f = list.get(first);
            Integer l = list.get(last);
            list.set(first, l);
            list.set(last, f);
            first += 1;
            last -= 1;
        }
        return list;
    }
}

/**
 * @author:韦鹏
 * @desc: 偷鸡取巧，每次都插入在list的第0个位置
 */
class Solution1_4 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while (listNode != null) {
            list.add(0, listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}